A computer operates by executing a program. A program is a set of logical operations that are executed in relation to a set of data. The data is specified with a physical address. The physical address is accessed by the computer, and the data stored at that physical address is processed in accordance with a specified logical operation of the program.
Different techniques are used to process a physical address. A set-associative memory structure uses a portion of the physical address to access a set of data blocks. Another segment of the physical address is then used for comparison with a tag field in each block of the set of data blocks. If the tag field of one of the blocks in the set of data blocks matches the physical address segment, then the data from that block is used for subsequent processing.
A set-associative memory structure stands in contrast to a fully-associative memory structure. In a fully-associative memory structure, the memory structure effectively has one set with a large number of blocks within the set. Data can be written to or read from any block in the single set. In a direct mapped memory structure, a large number of sets are defined, with each set including one block. Data can be written to or read from any of the sets of the direct mapped memory.
A cache memory is a memory structure that is used to store frequently accessed data. The advantage of a cache memory is that it is extremely fast. Consequently, it is highly desirable to keep frequently accessed data within a cache memory.
Cache memories typically utilize either a set-associative memory structure, fully-associative memory structure, or direct mapped memory structure. The present invention is directed toward a set-associative cache memory. The techniques of the invention are equally applicable to other set-associative memory structures, such as translation-lookaside buffers.
A cache memory is used in conjunction with the execution of one or more programs. Computers commonly run multiple programs. When a computer is running multiple programs, each program attempts to load its frequently used data into the cache memory. When control is switched from a first program to a second program, the second program loads its frequently used data into the cache memory, thereby overwriting the frequently used data of the first program. That is, as data from the second program is required in the cache, individual blocks that contain information from the first program are overwritten with information from the second program. When processing returns to the first program, the frequently used data of the first program is no longer in the cache memory. Consequently, the frequently used data of the first program must be reloaded into the cache memory. Of course, this overwrites the frequently used data of the second program, necessitating the re-loading of this data when the second program is called at a later time.
Substitution of cache memory information produces processing delays. Thus, it would be highly desirable to provide a technique for reducing the processing delays associated with the overwriting of frequently used data in a cache memory of a computer that is running multiple programs. It would also be desirable to apply the technique to other set-associative memory structures, such as translation-lookaside buffers.